مترجم: حبیب الله علیخانی
منبع:راسخون




 

پروتکل های مبتنی بر ساختار شبکه

ساختار شبکه های اساسی می تواند نقش مهمی در عملیات پروتکل مسیر یابی در WSN را ایفا کند. در این بخش ما جزئیات بسیاری از پروتکل هایی که در این دسته قرار می گیرند را بررسی می کنیم.
پروتکل های مسیریابی بر اساس ساختار شبکه در زیر به سه دسته تقسیم شده :
1. مسیریابی مسطح یا یکدست(flat-based)
2. مسیریابی سلسله مراتبی (hierarchical-based)
3. مسیریابی مکانی(location-based)

مسیریابی مسطح(Flat Routing)

اولین دسته ازپروتکل های مسیریابی، پروتکل های مسیریابی مسطح multihop(چند گامه) هستند. در شبکه ی مسطح، هر گره به طور معمول نقش یکسانی را بازی می کنند و گره های سنسور برای انجام عمل سنس همکاری می کنند. با توجه به تعداد زیاد این گره ها این عملی نیست که به هر گره یک شناسه گلوبال یا سراسری اختصاص دهیم. این نظر منجر به مسیریابی داده محور(data-centric) می شود که در آن BS (Base Station)پرسجوها را به نواحی خاصی ارسال می کند و منتظر داده از سنسورهای واقع در آن مناطق خاص می ماند. بعد از اینکه داده در حال درخواست از طریق پرسجو است، نامگذاری مبتنی بر ویژگی(attribute-based) لازم است تا خواص داده را مشخص کند. کارهای اولیه روی مسیریابی داده محور(به عنوان مثال SPIN و انتشار مستقیم) برای صرفه جویی انرژی از طریق مذاکره داده و حذف داده های اضافی نشان داده شده است. این دو پروتکل این انگیزه را می دهد تا بسیاری از پروتکل های دیگر که مفهوم مشابه را دنبال می کند را طراحی کنند. در ادامه ی این بخش، ما این پروتکل ها را به طور مختصر بیان می کنیم و مزایا و مسائل مربوط به عملکرد آنها را برجسته می کنیم.

پروتکل سنسور برای اطلاعات از طریق مذاکره:

پروتکل SPIN: یک خانواده از پروتکل های تطبیقی به نام پروتکل سنسور برای اطلاعات از طریق مذاکره(SPIN) را پیشنهاد شده که تمام اطلاعات در هر گره را به همه ی گره های دیگر شبکه منتشر می کند، به فرض اینکه همه ی گره ها در شبکه باالقوه ایستگاه اصلی(BS) هستند. این کاربر را قادر می سازد تا از هر گره پرسجو کند(query بفرستد) و بلافاصله اطلاعات مورد نیاز را دریافت کند. این پروتکل ها از این خاصیت استفاده می کنندکه گره هایی که در نزدیکی و مجاورت هم هستند داده ی مشابه دارند و از این رو نیاز است تا فقط اطلاعاتی را که سنسورهای دیگر ندارند توزیع کنند. پروتکل¬های خانواده SPINاز مذاکره ی داده و الگوریتم¬های های تطبیقی استفاده می¬کنند. گره¬هایی که SPIN را به کار می¬برند یک نام سطح بالا را برای توصیف کامل داده جمع¬اوری شده به کار می¬برند(متا دیتا یا فراداده یا داده درباره ی داده، نام دارد) و مذاکرات متا دیتا را قبل از اینکه هرگونه داده منتقل شود، انجام می دهد.
این تضمین می کند که هیچ داده اضافی در سراسر شبکه ارسال نمی شود. مفهوم فرمت متا دیتا برنامه ی خاصی است و در SPIN مشخص نشده است. برای مثال، اگر سنسورها یک ناحیه ی مشخص را پوشش دهند، ممکن است از شناسه ی (ID) منحصربفرد خود برای گزارش متا دیتا استفاده کنند. بعلاوه، SPIN به سطح انرژی فعلی گره آگاهی دارد و پروتکل را بسته به اینکه چقدر انرژی باقی مانده است سازگار می¬کند. این پروتکل ها در مد زمان محور(time-driven) کار می کنند و همه داده¬ها را حتی وقتی که یک کاربر درخواست هیچ داده¬ای را نداده است، در سطح شبکه توزیع می¬کنند. خانواده یSPIN طراحی شده تا از طریق مذاکره و انطباق منابع، مشکل پروتکل سیل آسا(flooding) کلاسیک را حل کند. پروتکل های خانواده ی SPIN بر اساس دو ایده ی اساسی طراحی شده است:
1- گره های سنسوری موثرتر عمل کنند و حفاظت انرژی با ارسال داده هایی که داده های سنسور را بجای ارسال تمام داده ها توصیف می کنند. برای مثال، تصویر و گره های سنسوری باید تغییرات در منابع انرژی خود را نظارت کنند.
2- پروتکل های متعارف مانند پروتکل سیل آسا یا پروتکل های مبتنی بر شایع پراکنی(gossiping-based) هنگام ارسال اضافی و کپی گرفتن غیرضروری داده ها توسط سنسور های پوشش مناطق متداخل(هم پوشانی)، انرژی و پهنای باند را هدر می دهند. اشکالات پروتکل سیل آسا شامل انفجاری است که بوسیله ی تکثیر ارسال پیام به گره های یکسان، هم پوشانی در زمانی که دو گره یک ناحیه ی یکسان را حس می کنند که بسته های مشابه را به گره همسایه ی مشابه ارسال می کند، و منابع کوری که مقادیر قابل توجهی از انرژی را بدون در نظر گرفتن محدودیت های انرژی، مصرف می کند. Gossiping برای ارسال بسته، بجای پخش کورکورانه بسته، از طریق انتخاب یک گره به صورت تصادفی، از مشکل انفجار جلوگیری می کند. اگرچه این کار باعث تاخیر در انتشار داده در بین گره ها می شود.
مذاکره متادیتا SPIN مشکلات پروتکل سیل آسا کلاسیک را حل می کند. در نتیجه باعث بهره وری انرژی می شود. SPIN یک پروتکل سه مرحله ای است در نتیجه گره های سنسوری از سه نوع پیام AVD، REQ و DATA برای برقراری ارتباط استفاده می کند. AVD برای تبلیغ داده های جدید استفاده می شود، REQ برای درخواست داده استفاده می شود و DATA پیام حقیقی است. وقتی که یک گره ی SPIN داده ی جدیدی بدست می آورد که مایل است آن را به اشتراک گذارد، پروتکل با انتشار یک پیام AVD حاوی متادیتا شروع می کند، اگر یک همسایه تمایل به داده داشته باشد، یک پیام REQ برای DATA ارسال می کند و DATA به این گره ی همسایه فرستاده می شود. سپس گره ی سنسور همسایه این فرآیند را با همسایگان خود تکرار می کند. در نتیجه، کل ناحیه ی سنسور یک کپی از اطلاعات دریافت خواهد کرد. پروتکل خانواده ی SPIN شامل تعداد زیادی از پروتکل ها می باشند. دو گروه اصلی آن SPIN-1 و SPIN-2 نامیده شده اند. آنها قبل از انتقال داده ها به منظور اطمینان از اینکه فقط اطلاعات مفید منتقل خواهد شد، مذاکره را انجام می دهند. همچنین هر گره مدیریت منبع خود را دارد که پیگیری مصرف منابع را اداره می کند و قبل از انتقال داده از گره ها نظرسنجی می شود. پروتکل SPIN-1 یک پروتکل سه مرحله ای است مانند آنچه که در بالا توضیح داده شده. یک بسط SPIN-1 ، SPIN-2 است که علاوه بر مذاکره، شامل یک منبع مبتنی بر آستانه(threshold-based) با مکانیزم اطلاع دهنده، می باشد. وقتی انرژی در گره ها فراوان است، SPIN-2 با استفاده از پروتکل سه مرحله ای SPIN-1 ارتباط برقرار می کند. اما، وقتی که انرژی در یک گره شروع می شود تا به آستانه ی پایین برسد، باعث می شود تا مشارکت آن در پروتکل کاهش یابد. به این صورت است که، زمانی مشارکت می کند که بتواند همه ی مراحل دیگر پروتکل را کامل کند بدون اینکه زیر پایین ترین حد آستانه ی انرژی برسد. در نتیجه، SPIN-1 و SPIN-2 پروتکل های ساده ای هستند که داده را به طور موثر و کارا منتشر می کند در حالیکه وضعیت هیچ همسایه را نگه نمی دارد. این پروتکل به خوبی مناسب محیط هایی که در آن سنسور ها متحرک هستند، می باشد چراکه تصمیم گیری ارسال آنها بر اساس اطلاعات همسایگی محلی است. پروتکل های دیگر خانواده ی SPIN:

• SPIN-BC : این پروتکل برای کانال های broadcast طراحی شده است.
• SPIN-PP : این پروتکل برای ارتباط نقطه به نقطه طراحی شده است(به عنوان مثال مسیریابی hop-by-hop گام به گام).
• SPIN-EC : این پروتکل مانند SPIN-PP عمل می کند با این تفاوت که یک رویه هیوریستیک(اکتشافی) انرژی به آن اضافه شده است.
• SPIN-RL : هنگامی که کانالی اتلاف زیادی داشته باشد، پروتکلی به نام SPIN-RL استفاده می شود که تنظیماتی برای بیان علت اتلاف آن کانال، به پروتکل SPIN-PP اضافه شده است.

یکی از مزایای SPIN این است که تغییرات توپولوژیکی محلی هستند از آنجایی که هر گره فقط باید همسایه های تک گامه (single-hop که با یک گام با آن فاصله دارند) را شناسایی کند. SPIN نسبت به پروتکل سیل آسا صرفه جویی انرژی بیشتری دارد و مذاکره ی متادیتا تقریبا نصف داده ی اضافی است. به هر حال، مکانیزم اعلان داده ی SPIN ها نمی تواند تحویل داده(دلیوری) را تضمین کند.
برای دیدن این موضوع، عمل تشخیص نفوذ را در نظر بگیرید که در آن داده ها باید به طور قابل اطمینان در پریود های زمانی
گزارش داده شوند و فرض کنیم که گره هایی که به داده نیاز دارند از گره ی مبدا دور هستند و گره های بین مبدا و گره ی مقصد به این داده احتیاج ندارند. چنین داده هایی به هیچ وجه به مقصد تحویل داده نخواهند شد.
در شكل زیر نمونه اي از ا ين پروتكل نشان داده شده است . با در يافت يك پيغام ADV از طر يق گره A ،گره B بررسي مي كند كه آ يا تمامي داده تبليغ شده را در اختيار دارد يا خير. در غير اين صورت ، گره B يك پيغام REQ به A بر مي گرداند كه در آن تمامي داده هايي كه گره B نياز دارد، فهرست شده است . وقتي گره A پيغام REQ را دريافت كرد، داده هاي درخواست شده را استخراج مي كند و آنها را بوسيله يك پيغام DATA به B ارسال مي كند. سپس گره B يك پيغام ADV جديد تو ليد مي كند كه در آن داده جديد به دست آمده را به همه همسايگانش تبليغ مي كند ولي پيغام ADV را براي گره A ارسال نمي كند، چون مي داند كه گره A قبلا داده مورد نظر را در اختيار دارد يا خير . سپس اين گره ها هم تبليغات مربوط به داده جديد را به همسايگانشان ارسال مي كنند و پروتكل ادامه مي يابد.
انتشار مستقیم: الگویی رایج از تراکم داده ها برای WSN ها که انتشار مستقیم نام دارد. انتشار مستقیم در اصل یک الگویDC (Data-Centric) و Application-Aware است که در ان تمام داده¬ی تولید شده به وسیله ی گره¬های سنسور توسط یک زوج مقدار و صفت.(attribute-value) تعریف می¬شود. هدف اصلی الگوی DC این است که داده¬ای که از منابع مختلف در مسیر می آید(در شبکه ی متراکم) را بوسیله ی حذف افزونگی و کم کردن تعداد انتقالات ترکیب کند که به این ترتیب انرژی شبکه دخیره می¬شود و طول عمر ان افزایش می¬یابد. برخلاف مسیریابی سنتی End-to-End ، مسیریابی DCمسیرها را از چندین مبدا به یک مقصد تنها پیدا می¬کند که اجازه ادغام داده¬های افزونه درون شبکه را نیز می¬دهد .
در انتشار مستقیم، سنسورها رویدادها را اندازه¬گیری کرده و گرادیان(جهت جریان) اطلاعات را به همسایه¬های مربوطه ایجاد می-کنند. ایستگاه اصلی(BS) داده را با Broadcast کردن(پخش کردن به همه) خواسته ها (interest) درخواست می¬کند. خواسته(interest)کاری را که باید توسط شبکه انجام شود توصیف می¬کند. Interest در سرتاسر شبکه به¬صورت گام به گام منتشر می¬شود و توسط هر گره به همسایه¬های همان گره منتشر می¬شود. در همین حال، مسیرها برای ارسال داده مورد قبول به سمت گره متقاضی ترسیم می¬گردند(یعنی ممکن است یک BS بوسیله ی انتشار interest و تکثیر گره های میانی این خواسته ها را برای داده پرسجو کند) . هر سنسور که Interestرا دریافت کرد یک گرادیان به سمت گره¬های سنسور که از انها Interestرا دریافت کرده بود ایجاد می¬کند. این فرایند تا زمانی که گرادیان¬ها از منابع به سمت ایستگاه اصلی ایجاد شوند ادامه پیدا می¬کند. به طورکلی یک گرادیان، یک مقدار صفت و یک مسیر را مشخص می¬کند. شدت گرادیان ممکن است به سمت همسایه¬های متفاوت با هم فرق کند، در نتیجه میزان جریان اطلاعات متفاوت وجود خواهد داشت. در این مرحله حلقه ها بررسی نشده اما در مرحله ی بعد حذف شده است. تصویر زیر مثالی از کار انتشار مستقیم را نشان می دهد(ارسال interest ها ، ایجاد گرادیان ها و انتشار داده).
زمانیکه interested ها به گرادیان ها مجهز شده اند، مسیر جریان اطلاعات از چندین مسیر شکل می گیرد و سپس بهترین مسیرها بر اساس یک قانون برای جلوگیری از سیل بیشتر تقویت می شوند. به منظور کاهش هزینه های ارتباطی، داده در مسیر جمع(خوشه بندی) شده است. هدف پیدا کردن یک درخت تجمع خوب که داده ها را از گره ی مبدا به گره مقصد می رساند. BS به طور متناوب جدید می شود و وقتی که شروع به دریافت داده از مبدا(ها) می کند، interest را دوباره می فرستد. این کار ضروری است به این دلیل که interest در سراسر شبکه به طور مطمئن منتقل نمی شوند.
همه ی گره های سنسوری در شبکه های انتشار مستقیم، application-aware(کار آگاه) هستند، که با انتخاب مسیر های تجربی خوب و با استفاده از ذخیره و پردازش داده در شبکه، موجب صرفه جویی انرژی در انتشار می شود. ذخیره سازی می تواند بهره وری، نیرومندی و مقیاس پذیری هماهنگی بین گره های سنسوری را افزایش دهد که الگوی انتشار داده است. مزیت دیگر انتشار مستقیم انتشار خودبخود یک رویداد مهم به برخی از بخش های شبکه ی سنسوری است. یک چنین بازیابی اطلاعات فقط با پرسجوهای پایدار متناسب است که در آن گره های درخواست کننده منتظر داده نیستند که این مسئله یک پرسجو را برای یک بازه زمانی ایفا می کند. این باعث می شود که آنرا برای پرسجوها یک بار نامناسب کند. بطوریکه تنظیم گرادیان برای پرسجو هایی که فقط یک بار از مسیر استفاده می کنند، ارزش ندارد .
عملکرد روش جمع آوری(خوشه بندی) داده ها مورد استفاده در الگوی انتشار مستقیم، تحت تاثیر عوامل متعددی قرار گرفته است. از جمله موقعیت گره های مبدا در شبکه، تعداد منابع و توپولوژی شبکه های ارتباطی. به منظور بررسی این عوامل، دو مدل از قرار دادن مبدا(در شکل بالا نشان داده شده است) مورد مطالعه قرار گرفته است . این مدل ها، مدل ER(شعاع رویداد) و مدل RS(منابع تصادفی) نامیده می شوند. در مدل ER، یک نقطه در منطقه ی شبکه به عنوان محل رویداد تعریف شده است. این نقطه ممکن است یک وسیله ی نقلیه یا برخی پدیده ی دیگر که توسط گره ی سنسوری در حال ردیابی باشد. همه ی گره ها با فاصله ی S از این رویداد (دامنه ی سنجش یا سنس نامیده می شود) که BS نیستند، در نظر گرفته می شود که منابع داده باشند. متوسط تعداد منابع در یک شبکه واحد با تعداد گره ی سنسوری n، تقریبا برابر S2n است. در مدل RS ، K از گره هایی که BS نیستند، به صورت تصادفی منابع باشند انتخاب می شوند . بر خلاف مدل ER، منابع لزوما در کنار یکدیگر خوشه بندی نیستند. در هر دو مدل قرار دادن منابع، برای یک بودجه انرژی معین، تعداد بیشتری از منابع می توانند به BS متصل شوند. به هر حال، هر یک بسته به کاربرد از نظر مصرف انرژی بهتر عمل می کنند. در نتیجه، صرفه جویی انرژی با تجمع داده(خوشه بندی) که در انتشار مستقیم استفاده شد، با توجه به پویایی در پدیده های حس شده، می تواند به درجه ی بیشتر نیرومندی تبدیل شود.
همچنین بار دیگر در شکل های زیرنحوه عملكرد اين الگوريتم به صورت خلاصه آورده شده است:
انتشار مستقیم از دو جنبه با SPIN متفاوت است. اول اینکه انتشار مستقیم داده¬های مورد پرس و ¬¬جو را بنا به درخواست مطرح می¬کند، به¬طوری¬که ایستگاه اصلی پرس و ¬جوها را با استفاده از روش سیل¬اسا بعضی از کارها به گره¬های سنسور می¬فرستد، اما در SPINسنسورها، موجود بودن داده موردتوجه گره¬ها را برای پرس و جوی ان داده اعلام می¬کنند. دوم اینکه همه ارتباطات در انتشار مستقیم به صورت همسایه به همسایه است و هر گره توانایی انجام تراکم داده و ذخیره¬سازی را دارد. برخلاف SPIN، در انتشار مستقیم نیازی به نگهداری توپولوژی سراسری شبکه نیست، اما در انتشار مستقیم، ممکن است کاربردهایی بطور مثال نظارت محیطی که نیاز به ادامه ارسال داده به ایستگاه اصلی دارند اعمال نشود، زیرا ممکن است مدل Query-drivenبنا به درخواست داده در این خصوص کمک نکند. علاوه براین تطبیق داده با Queryها ممکن است به بعضی از سربارهای اضافه در گره¬های سنسور نیاز داشته باشد.
Rumor routing : مسیریابی شایعه پراکنی یک روش تغییریافته از پروتکل انتشار مستقیم است و به طور عمده برای کاربرد هایی که مسیریابی جغرافیایی برای آن امکانپذیر نیست درنظر گرفته شده است. به طور کلی، انتشار مستقیم از روش سیل آسا(flooding) برای تزریق پرسجو به سراسر شبکه، در زمانیکه مقیاس جغرافیایی برای انتشار وجود نداشته باشد، استفاده می کند. اما، در برخی از موارد، تنها مقدار کمی از داده های درخواست شده از گره وجود دارد؛ بنابراین استفاده از روش سیل آسا ضروری نسیت. اگر تعداد رویدادها کم باشد و تعداد پرسجوها زیاد باشد، یک روش دیگر سیل(flood) رویدادها است. ایده ی کلیدی این است برای بازیابی اطلاعات درمورد وقوع رویداد، بجای اینکه به روش سیل آسا پرسجوها را سراسر شبکه پخش کنیم، به سمت گره هایی که رویداد خاصی را مشاهده کرده اند، حرکت دهیم. برای سیل رویدادها در شبکه، الگوریتم مسیریابی شایعه پراکنی بسته هایی با طول عمر بالا به نام agent (عامل) را به کار می گیرد. هنگامیکه یک گره رویداد خاصی را تشخیص داد، این رویداد را به جدول محلی خود که جدول رویداد نام دارد، اضافه می کند، و یک agent ایجاد می کند. agent در شبکه حرکت می کند تا اطلا عات درمورد رویداد محلی را به گره های دور منتشر کند. هنگامیکه گره ای یک پرسجو برای رویدادی تولید می کند، ممکن است گره هایی که مسیر را می دانند، با بررسی در جدول رویدادشان به آن پرسجو پاسخ دهند. بنابراین، نیازی نیست تا آن را درسراسر شبکه غرق(flood) کنیم، که این کار باعث کاهش هزینه ی ارتباطات می شود. از سوی دیگر، مسیریابی شایعه پراکنی فقط یک مسیر بین مبدا و مقصد برقرار می کند برعکس انتشار مستقیم که در آن داده ها می توانند از طریق چند مسیر با سرعت پایین حرکت کنند. نتایج شبیه سازی نشان داد که مسیر یابی شایعه پراکنی در مقایسه با رویداد سیل آسا، می تواند به طور قابل توجه ای در انرژی صرفه جویی کند و همچنین می تواند گره های معیوب را رسیدگی کند. با این وجود، مسیریابی شایعه پراکنی فقط زمانی که تعداد رویدادها کم باشد، خوب کار می کند. برای رویدادهای با تعداد بالا، اگر به اندازه کافی به این رویدادها از سمت BS (ایستگاه اصلی) علاقه مندی وجود نداشته باشد، هزینه ی نگهداری agentها و جداول رویداد در هر گره غیر ممکن می شود. علاوه بر این، سربار مربوط به مسیریابی شایعه پراکنی توسط پارامترهای مختلف مورد استفاده در الگوریتم هایی(مانند زمان زندگی(TTL) مربوط به پرسجوها و agentها) کنترل می شود. از آنجا که گره ای از طریق agent رویداد از رویدادها آگاه شد، جستجو برای تعیین مسیر یک agent رویداد، تاثیر بسیاری بر عملکرد انتخاب گام بعدی در مسیریابی شایعه پراکنی می گذارد.

الگوریتم کمترین هزینه ی ارسال(Minimum Cost Forwarding Algorithm):

الگوریتم کمترین هزینه ی ارسال(MCFA) این واقعیت را مورد بهره برداری قرار می دهد که جهت مسیریابی همیشه شناخته شده است(یعنی نسبت به BS ثابت بیرونی). از اینرو یک گره ی سنسوری نیاز دارد تا یک ID(شناسه) منحصربفرد داشته باشد نه اینکه از یک جدول مسیریابی نگهداری کند. در عوض هر گره حداقل برآورد هزینه از خودش تا BS را نگه می دارد. هر پیامی که توسط گره سنسوری ارسال می شود، به همه ی همسایگانش(broadcast می شود) داده می شود. هنگامیکه گره ای پیام را دریافت کرد، چک می کند که آیا در مسیری که کمترین هزینه را از گره ی سنسوری مبدا تا BS را دارد، واقع شده یا نه. اگر بود، آن گره نیز پیام را به همسایگان خودش ارسال می کند. این فرآیند تکرار می شود تا به BS برسد.
در MCFA، هر گره باید برآورد حداقل هزینه ی مسیر از خودش تا BS را بداند. این مطلب از طریق زیر بدست می آید. BS یک پیام را پخش(broadcast) می کند که هزینه ی آن را صفر قرار می دهد، در حالی که هر گره در ابتدا حداقل هزینه به BS را بینهایت () قرار می دهد. هر گره، بمحض دریافت پیام پخش شده از سوی BS، چک می کند تا ببیند که آیا برآورد در پیام به همراه لینک که دریافت کرده کمتر از برآورد فعلی است یا نه، اگر بود، برآورد فعلی و برآورد در پیام پخش شده به روزرسانی می شوند. اگر پیام پخشی دریافت شده بروزرسانی شود، دوباره فرستاده می شود; وگرنه، آن پاک می شود و کار دیگری انجام نمی دهد. اما، روش های قبلی ممکن است در بعضی از گره ها چندین بروزرسانی انجام دهند، و گره هایی که از BS دور هستند نسبت به گره های که به BS نزدیکترند، بیشتر بروزرسانی شوند. برای جلوگیری از این، MCFA در فاز راه اندازی به اجرای یک الگوریتم عقبگرد(backoff) اصلاح شد. الگوریتم عقبگرد دستور می دهد که یک گره پیام بروزرسانی را نمی فرستد تا اینکه از زمانی که در آن پیام بروز شده است، به مدت a * lc واحد زمانی سپری شود. a یک ثابت است و lc هزینه ی لینک که در آن پیام دریافت شده است می باشد.

مسیریابی مبتنی بر گرادیان(gradient-based):

نوع دیگری از انتشار مستقیم را پیشنهاد شده که مسیریابی مبتنی بر گرادیان (GBR) نامیده شده است. ایده ی اصلی در GBR این است که وقتی که درخواست ایستگاه پایه در کل شبکه پخش می شود، تعدادگام ها را به خاطر بسپارد. به این صورت که، هر گره سنسور تعداد گام های مورد نیاز برای رسیدن به ایستگاه پایه را محاسبه می کند و بدین وسیله می تواند کمترین تعداد گام برای رسیدن به ایستگاه پایه را که ارتفاع ان سنسور نامیده می شود را بدست اورد. اختلاف بین ارتفاع گره و سنسورهای همسایه ی خود به عنوان گرادیان مسیر بین انها در نظر گرفته می شود. پکت ها یا داده های هر سنسور توسط مسیرهایی که بالاترین گرادیان را دارند به ایستگاه پایه فرستاده می شوند. در واقع این روش تلاش می کند تا با تعداد گام-های کمتر داده را به ایستگاه پایه برساند. برای توزیع یکنواخت ترافیک روی شبکه در این پروتکل دو تکنیک ترکیب داده ها و پخش ترافیک به کار گرفته شده است. سنسورهایی که از چندین مسیر داده دریافت می کنند می توانند کار ترکیب داده ها را انجام دهند. در GBR سه تکنیک مختلف پخش ترافیک در زیر آمده است:
روش اتفاقی : اگر دو یا چند مسیر با گرادیان یکسان وجود داشته باشند، انتخاب مسیر به صورت تصادفی خواهد بود.
روش انرژی : وقتی که انرژی یک سنسور از یک استانه معین پایین تر می اید، ارتفاع خود را افزایش می دهد و بدین وسیله به سنسورهای دیگر می فهماند که تا حد امکان از این سنسور برای انتقال داده کمتر استفاده شود.
روش جریان داده : این روش تلاش می کند تا مسیرهایی که در حال حاضر برای انتقال داده ها استفاده می شوند، برای مسیرهای جدید به کار گرفته نشوند.
با بکارگیری روش های بالا ترافیک در کل شبکه پخش می شود و در نتیجه طول عمر شبکه افزایش پیدا می کند، همچنین این روش ها را می توان در پروتکل های دیگر نیز به کار برد. نتایج شبیه سازی ها نشانگر ان است که GBR از نظر مصرف انرژی موثرتر از انتشار مستقیم کار می کند.
پرسجوی سنسور اطلاعات- محور و مسیریابی انتشار ناهمسانگرد اجباری:
دو روش پرسجوی سنسور اطلاعات-محور(IDSQ) و مسیریابی انتشار ناهمسانگرد اجباری(CADR) ، در قبل پیشنهاد شده بود. اهداف CADR یک شکل کلی انتشار مستقیم می باشد. ایده ی کلی پرسجوی سنسورها و حرکت دادن داده ها در شبکه است به طوریکه بدست آوردن اطلاعات حداکثر باشد در حالی که تاخیر و پهنای باند به حداقل می رسد. CADR با استفاده از یک مجموعه معیارها، برای انتخاب اینکه کدام سنسورها می توانند داده را دریافت کنند، پرسجوها را منتشر می کند. این کار فقط با فعال کردن سنسورها یی که نزدیک به یک رویداد خاص هستند و به صورت پویا مسیرهای داده را تنظیم می کند، انجام می شود. تفاوت اصلی این روش با انتشار مستقیم علاوه بر هزینه های ارتباط در نظرگرفتن بدست آوردن اطلاعات است. در CADR، هر گره یک هدف اطلاعات/هزینه ارزیابی می کند و داده را براساس گرادیان اطلاعات/هزینه محلی و نیاز کاربر نهایی حرکت می دهد. تئوری برآورد برای مدل سازی سودمندی اطلاعات مورد استفاده قرار گرفت. در IDSQ گره پرس و جو می تواند تعیین کند که گره می تواند مفیدترین اطلاعات را با امتیاز تعادل هزینه ی انرژی ارائه دهد. با این حال، IDSQ صریحا تعیین نمی کند که چگونه پرسجو و اطلاعات بین سنسورها و BS ها حرکت می کنند. بنابراین، IDSQ می تواند به عنوان مکمل روش بهینه سازی دیده شود. نتایج شبیه سازی نشان داده که این رویکرد بیشتر از انتشار مستقیم که در آن پرسجوها در یک مد همگرا(دارای خواص برابر) منتشر می شوند و اولین بار به نزدیکترین همسایه می رسند، بهره وری انرژی بیشتری دارد.
COUGAR : یکی دیگر از پروتکل های داده محور که cougar نام دارد، به شبکه به عنوان یک سیستم پایگاه داده ای توزیع شده ی بزرگ نگاه می کند. ایده ی کلی، استفاده از پرسجوهای اعلانی به منظور پردازش پرسجوی انتزاعی از وظایف لایه های شبکه است، مانند انتخاب سنسورهای مربوطه و غیره. بکاربردن cougar در شبکه ی خوشه بندی برای صرفه جویی بیشتر در مصرف انرژی می باشد. انتزاع از طریق لایه ی اضافی پرسجوی پشتیبانی شده که بین لایه ی شبکه و اپلیکیشن پنهان است. Cougar یک معماری برای سیستم پایگاه داده ای سنسوری در نظر می گیرد که در آن گره های سنسوری یک گره ی لیدر برای انجام خوشه بندی و انتقال داده به BS انتخاب می کند. BS مسئول طرح ریزی یک پرسجو است که اطلاعات ضروری در باره ی جریان داده و محاسبات داخل شبکه ای برای پرسجوی وارده را مشخص می کند، و این را به گره های مربوطه ارسال می کند. همچنین طرح پرسجو چگونگی انتخاب یک لیدر برای پرسجو را توصیف می کند. این معماری قابلیت محاسبات درون شبکه ای را فراهم می کند و زمانیکه داده های تولید شده بزرگ است، باعث بهره وری انرژی شود. cougar یک متد لایه شبکه ی مستقل برای پرسجوی داده ارائه می کند. با این وجود، cougar یک سری اشکالات هم دارد. اول، علاوه بر یک لایه پرسجو، بر روی هر گره ی سنسوری ممکن است سربار اضافی از نظر مصرف انرژی و ذخیره سازی حافظه اضافه شود. دوم، برای کسب موفقیت در محاسبات داده داخل شبکه ای، قبل از ارسال داده به گره ی لیدر، هماهنگ سازی میان گره ها لازم است(نه اینکه در همان زمان همه ی داده ها از منابع ورودی دریافت می شود). سوم، گره ی لیدر برای جلوگیری از اینکه آنها نقاط حاد شوند(معرض شکست)، باید به صورت پویا پشتیبانی شوند.
ACQUIRE : تکنیکی برای پرسجوی شبکه های سنسوری که ارسال Active Qwery در شبکه های سنسوری (ACQUIRE)نامیدند، پیشنهاد شده است. مشابه COUGAR ، ACQUIRE به شبکه به عنوان پایگاه داده ی توزیع شده نگاه می کند. که در آن پرسجوهای پیچیده می توانند به چندین زیر پرسجو(پرسجوهای کوچکتر) تقسیم شوند. عملیات ACQUIRE می توانند به شرح زیر توصیف شوند. گره ی BS یک پرسجو می فرستد، که سپس توسط هر گره دریافت کننده ی پرسجو، ارسال می شود. در طی این جریان، هر گره تلاش می کند که به قسمتی از پرسجو با استفاده از اطلاعات مخزن(اطلاعاتی که داشت) پاسخ دهد و سپس آن را به گره ی سنسوری دیگر منتقل کند. اگر اطلاعات مخزن بروز نبود، گره ها اطلاعات را از همسایگان خود با یک پیش بینی(lookahead) از d گام، جمع آوری می کند. پس از اینکه پرسجو به طور کامل حل شد،یا به طریق معکوس و یا کوتاهترین مسیر به BS، به عقب فرستاده می شود. از اینرو ACQUIRE می تواند پرسجوهای پیچیده را از طریق اجازه دادن به بسیاری از گره ها برای ارسال پاسخ ها، رسیدگی کند. توجه داشته باشید به دلیل ملاحضات انرژی انتشار مستقیم ممکن نیست برای پرسجوهای پیچیده استفاده شود. به طوریکه انتشار مستقیم از یک مکانیزم سیل آسا برای پرسجو های انبوه و پیوسته استفاده می کند. از سوی دیگر، ACQUIRE می تواند با تنطیم مقدار پارامتر پیش بینی d پرسجوهای کارآمد ارائه کند. وقتی که d با قطر شبکه برابر باشد، ACQUIRE مشابه سیل اسا رفتار می کند. اما اگر d خیلی کوچک باشد، پرسجو باید با گام های بیشتری حرکت کند. مدل سازی ریاضی برای پیدا کردن یک مقدار بهینه پارامتر d برای یک شبکه ی سنسوری که در آن هر گره دارای چهار همسایه بی واسطه دارد، استفاده شده است. با این وجود، نتایج شبیه سازی هیچ اعتباری ندارد. برای انتخاب گره ی بعدی در ارسال پرسجو، ACQUIRE یا آن را به صورت تصادفی برمی گزیند و یا انتخاب بر اساس حداکثر رضایتمندی پرسجو می باشد. به یاد آورید که هم انتخاب گره ی بعدی براساس کسب اطلاعات(CADR و IDSQ) و هم خود پرسجو، به گره ای فرستاده می شود که مسیر رویداد شناسایی شده را می داند(مسیر یابی شایعه پراکنی).
مسیریابی EAR(Energy-Aware Routing)
هدف مسیریابی EAR ، یک پروتکل انفعالی مقصدگرا، افزایش طول عمر شبکه است. اگرچه این پروتکل شبیه انتشار مستقیم می باشد، از این لحاظ متفاوت است که بجای حفظ یا اجرای یک مسیر بهینه در نرخ های بالاتر، مجموعه ای از مسیرها را حفظ می کند. این مسیرها با استفاده از یک تابع احتمال معین انتخاب و حفظ می شود. مقدار این احتمال بستگی به این دارد که چگونه هر مسیر می تواند به مصرف انرژی پایین دست یابد. با داشتن انتخاب مسیرها در زمانهای مختلف، انرژی هر مسیر مجزا زود تخلیه نمی شود. این امر می تواند طول عمر شبکه را هنگامیکه انرژی در میان تمام گره ها به طور به یک اندازه ازبین می رود، افزایش دهد. مهمترین پارامتری که در طراحی این پروتکل مدنظر گرفته شده¬است بقای شبکه می¬باشد. در این پروتکل فرض می شود که هر گره از طریق آدرس دهی مبتنی بر کلاس(class-based) که شامل محل و نوع گره می باشد، آدرس پذیر است. این پروتکل ارتباطی را از طریق روش سیل آسا محلی آغاز می کند که این ارتباط در کشف همه ی مسیرها بین جفت منبع/مقصد و هزینه هایشان استفاده می شود، بنابراین جدول مسیریابی ایجاد می شود. مسیرهای با هزینه ی بالا دور انداخته می شوند، و یک جدول ارسال با انتخاب گره های همسایه متناسب با هزینه شان، ساخته می شود. سپس جداول ارسال برای ارسال داده به مقصد با احتمال معکوس متناسب با هزینه ی گره استفاده می شود. روش سیل آسای محلی برای زنده نگه داشتن مسیر توسط گره ی مقصد اجرا می شود. اما این روش به جمع آوری(خوشه بندی) اطلاعات و راه اندازی مکانیزم آدرس دهی برای گره ها نیاز دارد، که راه اندازی مسیرهای پیچیده با انتشار مستقیم مقایسه می شود.

پروتکل های مسیریابی با گام های تصادفی:

هدف تکنیک مسیریابی مبتنی بر گامهای تصادفی، دستیابی به موازنه ی بار در یک مفهوم اماری با استفاده از چندین مسیریابی در شبکه ی سنسوری بیسم است. این تکنیک در شبکه های با مقیاس بزرگ که در آن گره ها تحرک بسیار محدودی دارند، در نظر گرفته شد. در این پروتکل، فرض بر این است که گره های سنسوری به طور تصادفی خاموش یا روشن شوند. علاوه براین، هر گره دارای یک شناسه ی منحصربفرد است اما هیچ اطلاعات محل مورد نیاز نیست. گره ها مرتب شده بودند به طوریکه هر گره دقیقا از یک نقطه ی تلاقی از یک شبکه ی منظم در یک صفحه می افتد، اما توپولوژی می تواند نامنظم باشد. برای پیدا کردن یک مسیر از منبع به مقصد، اطلاعات محل یا هماهنگی شبکه بوسیله ی محاسبه ی فاصله بین گره ها با استفاده از نسخه ی ناهمزمان(آسنکرون) توزیع شده ی الگوریتم معروف بلمن فورد، بدست آمده. گره های میانی ممکن است به عنوان گام بعدی گره های همسایه انتخاب می شوند که با توجه به احتمال محاسبه شده، به مقصد نزدیکتر اند. با اداره ی دقیق این احتمال، بعضی از انواع توازن بار در شبکه می تواند بدست آید. هنگامیکه لازم باشدگره ها اطلاعات وضعیت کمی را نگهداری کنند، الگوریتم مسیریابی ساده است. علاوه بر این، در زمان های مختلف مسیرهای مختلفی حتی برای همان منبع و گره های مقصد انتخاب می شوند. با این وجود، نگرانی اصلی در مورد این پروتکل این است که توپولوژی شبکه ممکن است عملی نباشد.

/ج